﻿#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <numeric>

using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	
};

class Solution {
public:
	typedef long long ll;
	void insert(vector<int>& sort_vec, int num) {
		int left = 0;
		int right = sort_vec.size() - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (sort_vec[mid] > num)
				right = mid - 1;
			else
				left = mid + 1;
		}
		sort_vec.insert(sort_vec.begin() + left, num);
	}
	vector<int> numsGame(vector<int>& nums) {
		int midnum = 0;
		int lastmid = 0;
		ll oneans = 0;
		vector<int> ans;
		ans.push_back(0);
		vector<int> sort_vec;
		sort_vec.push_back(nums[0]);
		for (int i = 1; i < nums.size(); i++) {
			insert(sort_vec, nums[i] - i);
			int mid = (sort_vec.size() - 1) / 2;
			midnum = sort_vec[mid];
			nums[i] = nums[i] - i;
			/*if(nums[i] < lastmid){
				oneans += abs(nums[i] - sort_vec[mid + 1]);
			}
			else
				oneans += abs(nums[i] - midnum);*/
			if (sort_vec.size() % 2 == 0) {
				if (nums[i] < lastmid)
					oneans += abs(nums[i] - sort_vec[mid + 1]);
				else
					oneans += abs(nums[i] - midnum);
			}
			else
				oneans += abs(nums[i] - sort_vec[mid]);
			ans.push_back(oneans % 1000000007);
			lastmid = midnum;
		}
		return ans;
	}
};

int main()
{
	Solution sol;
	vector<int> test = { 1,1,1,2,3,4 };
	vector<int> test2 = { 5, 4, 9, 6, 20, 25, 15 };
	sol.numsGame(test);
	cout <<endl;
}
